class Solution {//leetcode332——零钱兑换
public:
    int coinChange(vector<int>& coins, int amount) {
        int n=coins.size();
        vector<int> dp(amount+1,-1);
        dp[0]=0;

        for(int i=1;i<n+1;i++){
            for(int j=coins[i-1];j<amount+1;j++){
                if(dp[j-coins[i-1]]!=-1)
                    dp[j] = dp[j]==-1? dp[j - coins[i - 1]] + 1:min(dp[j], dp[j - coins[i - 1]] + 1);
            }
        }
        return dp[amount];
    }
};